/* Copyright (C) 1997-2005, Antony L Hosking.
 * All rights reserved.  */
package Translate;

import Translate.Exp.Ex;
import Translate.Temp.*;
import Translate.Tree.Exp.CONST;
import Translate.Tree.Stm.CJUMP;

import java.beans.FeatureDescriptor;
import java.io.*;
import java.util.*;

import Absyn.MiniJava.Stm;
import Absyn.MiniJava.SwitchBlock;
import Absyn.MiniJava.Stm.Switch;
import Semant.Type.*;

public class MiniJava extends Absyn.MiniJava.Visitor<Void, Exp> {
	private static void usage() {
		throw new Error("Usage: java Translate.MiniJava "
				+ "[ -target= Mips|PPCDarwin|PPCLinux ] <source>.java");

	}

	public static void main(String[] argv) throws java.io.IOException {
		Frame frame = new Mips.Frame();
		String mainClass = null;
		if (argv.length < 1)
			usage();
		if (argv.length > 1)
			for (String arg : argv) {
				if (arg.startsWith("-main="))
					mainClass = arg.substring(6);
				else if (arg.equals("-target=Mips"))
					frame = new Mips.Frame();
				else if (arg.equals("-target=PPCDarwin"))
					frame = new PPC.Frame.Darwin();
				else if (arg.equals("-target=PPCLinux"))
					frame = new PPC.Frame.Linux();
				else if (arg.startsWith("-"))
					usage();
			}
		String src = argv[argv.length - 1];
		Parse.MiniJava parse =
			new Parse.MiniJava(new java.io.FileInputStream(src));
		Absyn.MiniJava.Unit unit;
		try {
			unit = parse.CompilationUnit();
		} catch (Parse.ParseException e) {
			System.err.println(e.getMessage());
			return;
		} catch (Parse.TokenMgrError e) {
			System.err.println(e.getMessage());
			return;
		}
		Semant.MiniJava semant = new Semant.MiniJava(mainClass);
		Semant.Type types = unit.accept(semant, null);
		if (semant.anyErrors)
			return;
		MiniJava translate = new MiniJava(unit, types, mainClass, frame);
		PrintWriter out = new PrintWriter(System.out);
		for (Frag f : translate.results()) {
			out.println(f);
			out.flush();
		}
	}

	private final Semant.Type types;
	private Frame frame;

	public MiniJava(Absyn.MiniJava.Unit unit, Semant.Type t, String mainClass,
			Frame f) {
		types = t;
		frame = f;

		unit.accept(this, null);

		if (mainClass == null)
			return;

		// generate code for main method
		{
			frame = frame.mainFrame();
			varEnv.beginScope();
			// args = new String[argc] { argv[0], ..., argv[argc-1] }
			Tree.Exp _argc = frame.allocFormal(new Temp("_argc")).exp();
			Tree.Exp _argv = frame.allocFormal(new Temp("_argv")).exp();
			Temp argc = new Temp();
			Temp argv = new Temp();
			Temp args = new Temp();
			int wordSize = frame.wordSize();
			Label loop = new Label();
			Label exit = new Label();
			Temp p = new Temp();
			Tree.Stm body =
				SEQ(MOVE(TEMP(argc), _argc), //
						MOVE(TEMP(argv), _argv), //
						MOVE(TEMP(argc), SUB(TEMP(argc), CONST(1))), //
						MOVE(TEMP(args), //
								CALL(NAME(Label.get("new")), //
										Exps(MUL(TEMP(argc), CONST(wordSize)), //
												TEMP(argc)))), //
												MOVE(TEMP(p), TEMP(args)), //
												MOVE(TEMP(argv), ADD(TEMP(argv), CONST(wordSize))), //
												MOVE(TEMP(argc), SUB(TEMP(argc), CONST(1))), //
												BLT(TEMP(argc), CONST(0), exit, loop), //
												LABEL(loop), //
												MOVE(MEM(TEMP(p)), MEM(TEMP(argv))), //
												MOVE(TEMP(p), ADD(TEMP(p), CONST(wordSize))), //
												MOVE(TEMP(argv), ADD(TEMP(argv), CONST(wordSize))), //
												MOVE(TEMP(argc), SUB(TEMP(argc), CONST(1))), //
												BLT(TEMP(argc), CONST(0), exit, loop), //
												LABEL(exit), //
												ESTM(CALL(NAME(Label.get(mainClass + ".main")), //
														Exps(TEMP(args)))));
			varEnv.endScope();
			frags.add(new Frag.Proc(body, frame));
		}

		// generate code for helper functions
		{
			frame = frame.newFrame("new");
			varEnv.beginScope();
			Tree.Exp _size = frame.allocFormal(new Temp("_size")).exp();
			Tree.Exp _head = frame.allocFormal(new Temp("_head")).exp();
			Temp size = new Temp();
			Temp head = new Temp();
			Temp p = new Temp();
			int wordSize = frame.wordSize();
			Tree.Stm body =
				SEQ(MOVE(TEMP(size), _size), //
						MOVE(TEMP(head), _head), //
						MOVE(TEMP(p), //
								CALL(frame.external("malloc"), //
										Exps(ADD(CONST(wordSize), TEMP(size))))), //
										MOVE(MEM(TEMP(p)), TEMP(head)), //
										MOVE(TEMP(p), ADD(TEMP(p), CONST(wordSize))), //
										ESTM(CALL(frame.external("bzero"), //
												Exps(TEMP(p), TEMP(size)))), //
												MOVE(frame.RV(), TEMP(p)));
			varEnv.endScope();
			frags.add(new Frag.Proc(body, frame));
		}
		{
			frame = frame.newFrame("badPtr");
			varEnv.beginScope();
			Label msg = stringLabel("Attempt to use a null pointer");
			Tree.Stm body =
				SEQ(ESTM(CALL(frame.external("puts"), Exps(NAME(msg)))),
						ESTM(CALL(frame.external("exit"), Exps(CONST(1)))));
			varEnv.endScope();
			frags.add(new Frag.Proc(body, frame));
		}

		{
			frame = frame.newFrame("badSub");
			varEnv.beginScope();
			Label msg = stringLabel("Subscript out of bounds");
			Tree.Stm body =
				SEQ(ESTM(CALL(frame.external("puts"), Exps(NAME(msg)))),
						ESTM(CALL(frame.external("exit"), Exps(CONST(1)))));
			varEnv.endScope();
			frags.add(new Frag.Proc(body, frame));
		}
	}

	static Tree.Exp MEM(Tree.Exp exp) {
		return new Tree.Exp.MEM(exp, CONST(0));
	}

	static Tree.Exp MEM(Tree.Exp exp, int i) {
		return new Tree.Exp.MEM(exp, CONST(i));
	}

	static Tree.Exp TEMP(Temp temp) {
		return new Tree.Exp.TEMP(temp);
	}

	static Tree.Exp ESEQ(Tree.Stm stm, Tree.Exp exp) {
		return (stm == null) ? exp : new Tree.Exp.ESEQ(stm, exp);
	}

	static Tree.Exp NAME(Label label) {
		return new Tree.Exp.NAME(label);
	}

	static Tree.Exp.CONST CONST(int value) {
		return new Tree.Exp.CONST(value);
	}

	private static Tree.Exp[] Exps(Tree.Exp... a) {
		return a;
	}

	Tree.Exp CALL(Tree.Exp f, Tree.Exp[] a) {
		if (a.length > frame.maxArgsOut)
			frame.maxArgsOut = a.length;
		return new Tree.Exp.CALL(f, a);
	}

	static Tree.Exp ADD(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.ADD, l, r);
	}

	static Tree.Exp AND(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.AND, l, r);
	}

	static Tree.Exp DIV(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.DIV, l, r);
	}

	static Tree.Exp DIVU(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.DIVU, l, r);
	}

	static Tree.Exp MUL(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.MUL, l, r);
	}

	static Tree.Exp OR(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.OR, l, r);
	}

	static Tree.Exp SLL(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.SLL, l, r);
	}

	static Tree.Exp SRA(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.SRA, l, r);
	}

	static Tree.Exp SRL(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.SRL, l, r);
	}

	static Tree.Exp SUB(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.SUB, l, r);
	}

	static Tree.Exp XOR(Tree.Exp l, Tree.Exp r) {
		return new Tree.Exp.BINOP(Tree.Exp.BINOP.Operator.XOR, l, r);
	}

	static Tree.Stm SEQ(Tree.Stm l, Tree.Stm r) {
		if (l == null)
			return r;
		if (r == null)
			return l;
		return new Tree.Stm.SEQ(l, r);
	}

	static Tree.Stm SEQ(Tree.Stm... a) {
		Tree.Stm stm = null;
		for (Tree.Stm s : a)
			stm = SEQ(stm, s);
		return stm;
	}

	static Tree.Stm LABEL(Label label) {
		return new Tree.Stm.LABEL(label);
	}

	static Tree.Stm JUMP(Label target) {
		return new Tree.Stm.JUMP(target);
	}

	static Tree.Stm MOVE(Tree.Exp d, Tree.Exp s) {
		return new Tree.Stm.MOVE(d, s);
	}

	static Tree.Stm ESTM(Tree.Exp exp) {
		return new Tree.Stm.ESTM(exp);
	}

	static Tree.Stm BEQ(Tree.Exp l, Tree.Exp r, Label t, Label f) {
		return new Tree.Stm.CJUMP(Tree.Stm.CJUMP.Operator.BEQ, l, r, t, f);
	}

	static Tree.Stm BGE(Tree.Exp l, Tree.Exp r, Label t, Label f) {
		return new Tree.Stm.CJUMP(Tree.Stm.CJUMP.Operator.BGE, l, r, t, f);
	}

	static Tree.Stm BGT(Tree.Exp l, Tree.Exp r, Label t, Label f) {
		return new Tree.Stm.CJUMP(Tree.Stm.CJUMP.Operator.BGT, l, r, t, f);
	}

	static Tree.Stm BLE(Tree.Exp l, Tree.Exp r, Label t, Label f) {
		return new Tree.Stm.CJUMP(Tree.Stm.CJUMP.Operator.BLE, l, r, t, f);
	}

	static Tree.Stm BLT(Tree.Exp l, Tree.Exp r, Label t, Label f) {
		return new Tree.Stm.CJUMP(Tree.Stm.CJUMP.Operator.BLT, l, r, t, f);
	}

	static Tree.Stm BNE(Tree.Exp l, Tree.Exp r, Label t, Label f) {
		return new Tree.Stm.CJUMP(Tree.Stm.CJUMP.Operator.BNE, l, r, t, f);
	}

	private LinkedList<Frag> frags = new LinkedList<Frag>();

	public List<Frag> results() {
		return frags;
	}

	private Symbol.Table<String, Frame.Access> varEnv =
		new Symbol.Table<String, Frame.Access>();

	private CLASS currentClass;

	public Exp visit(Absyn.MiniJava.Unit u, Void _) {
		for (Absyn.MiniJava.Dec.Class t : u.types)
			t.accept(this, _);
		return null;
	}

	private static LinkedHashMap<String, Label> vtable(INSTANCE i) {
		LinkedHashMap<String, Label> vtable;
		if (i.instanceOf.parent == null)
			vtable = new LinkedHashMap<String, Label>();
		else
			vtable = vtable(i.instanceOf.parent.instance);
		for (String method : i.methods.map.keySet())
			vtable.put(method, Label.get(i.instanceOf.name + "." + method));
		return vtable;
	}

	public Exp visit(Absyn.MiniJava.Dec.Class d, Void _) {
		CLASS c = currentClass = (CLASS) types.field(d.id.toString());
		int fields = c.fields.map.size();
		if (fields > 0)
			frags.add(new Frag.Data(frame.record(Label.get(d.id.toString()),
					fields)));
		String vtable =
			frame.vtable(Label.get(c.instance + "..vtable"),
					vtable(c.instance).values());
		frags.add(new Frag.Data(vtable));
		for (Absyn.MiniJava.Dec m : d.members)
			m.accept(this, _);
		return null;
	}

	private Tree.Exp thisExp;
	private Tree.Exp superExp = CONST(0);
	private Label returnLabel;

	public Exp visit(Absyn.MiniJava.Dec.Method m, Void _) {
		if (m.body == null)
			return null;
		frame = frame.newFrame(currentClass.name + "." + m.id);
		varEnv.beginScope();
		returnLabel = new Label();
		thisExp = null;
		if (currentClass.instance.method(m.id.toString()) != null)
			thisExp = frame.allocFormal(new Temp("_this")).exp();
		Tree.Stm body =
			SEQ(visit(m.formals, _), m.body.accept(this, _).unNx(),
					LABEL(returnLabel));
		varEnv.endScope();
		frags.add(new Frag.Proc(body, frame));
		return null;
	}

	public Exp visit(Absyn.MiniJava.Dec.Field f, Void _) {
		return null;
	}

	public Exp visit(Absyn.MiniJava.Dec.Formal f, Void _) {
		varEnv.put(f.id.toString(), frame.allocFormal(new Temp("_" + f.id)));
		return new Exp.Nx(null);
	}

	public Exp visit(Absyn.MiniJava.Dec.Var v, Void _) {
		Tree.Exp init =
			(v.init == null) ? CONST(0) : v.init.accept(this, _).unEx();
			Frame.Access a = frame.allocLocal(new Temp("_" + v.id));
			varEnv.put(v.id.toString(), a);
			return new Exp.Nx(MOVE(a.exp(), init));
	}

	public Exp visit(Absyn.MiniJava.Type.Class t, Void _) {
		return new Exp.Nx(null);
	}

	public Exp visit(Absyn.MiniJava.Type.Primitive t, Void _) {
		return new Exp.Nx(null);
	}

	public Exp visit(Absyn.MiniJava.Type.Array t, Void _) {
		return new Exp.Nx(null);
	}

	public Exp visit(Absyn.MiniJava.Exp.Assign e, Void _) {
		return new Exp.Nx(MOVE(e.left.accept(this, _).unEx(),
				e.right.accept(this, _).unEx()));
	}

	public Exp visit(Absyn.MiniJava.Stm.Block b, Void _) {
		varEnv.beginScope();
		Tree.Stm body = visit(b.stms, _);
		varEnv.endScope();
		return new Exp.Nx(body);
	}

	public Exp visit(Absyn.MiniJava.Stm.Dec s, Void _) {
		return s.dec.accept(this, _);
	}

	public Exp visit(Absyn.MiniJava.Stm.Break s, Void _) {
		return new Exp.Nx(JUMP(currentExit));
	}

	public Exp visit(Absyn.MiniJava.Stm.Continue s, Void _) {
		return new Exp.Nx(JUMP(currentNext));
	}

	public Exp visit(Absyn.MiniJava.Stm.Exp s, Void _) {
		if (s.exp != null)
			return s.exp.accept(this, _);
		return new Exp.Nx(null);
	}

	public Exp visit(Absyn.MiniJava.Stm.If s, Void _) {
		Exp exp1 = s.test.accept(this, _);
		Exp exp2 = s.thenStm.accept(this, _);
		Exp exp3 =
			(s.elseStm == null) ? new Exp.Nx(null) : s.elseStm.accept(this, _);
			return new Exp.Cx.IfThenElseExp(exp1, exp2, exp3);
	}

	public Exp visit(Absyn.MiniJava.Stm.Return s, Void _) {
		if (s.exp == null)
			return new Exp.Nx(JUMP(returnLabel));
		Tree.Exp exp = s.exp.accept(this, _).unEx();
		return new Exp.Nx(SEQ(MOVE(frame.RV(), exp), JUMP(returnLabel)));
	}

	private Label currentExit = null;
	private Label currentNext = null;

	public Exp visit(Absyn.MiniJava.Stm.While s, Void _) {
		Label next = new Label();
		Label body = new Label();
		Label exit = new Label();

		Tree.Stm exp = s.test.accept(this, _).unCx(body, exit);

		Label oldNext = currentNext;
		Label oldExit = currentExit;
		currentNext = next;
		currentExit = exit;
		Tree.Stm stm = SEQ(s.body.accept(this, _).unNx(), JUMP(next));
		currentNext = oldNext;
		currentExit = oldExit;

		return new Exp.Nx(SEQ(LABEL(next), exp, LABEL(body), stm, LABEL(exit)));
	}

	public Exp visit(Absyn.MiniJava.Stm.DoWhile s, Void _) {
		Label next = new Label();
		Label body = new Label();
		Label exit = new Label();

		Tree.Stm exp = s.test.accept(this, _).unCx(body, exit);

		Label oldNext = currentNext;
		Label oldExit = currentExit;
		currentNext = next;
		currentExit = exit;
		Tree.Stm stm = SEQ(s.body.accept(this, _).unNx(), JUMP(next));
		currentNext = oldNext;
		currentExit = oldExit;

		return new Exp.Nx(SEQ(LABEL(body), stm, LABEL(next), exp, LABEL(exit)));
	}

	public Exp visit(Absyn.MiniJava.Stm.For s, Void _) {
		Label test = new Label();
		Label next = new Label();
		Label body = new Label();
		Label exit = new Label();

		varEnv.beginScope();

		Tree.Stm init = visit(s.init, _);
		Tree.Stm exp =
			s.test == null ? null : s.test.accept(this, _).unCx(body, exit);
		Tree.Stm update = visit(s.update, _);

		Label oldNext = currentNext;
		Label oldExit = currentExit;
		currentNext = next;
		currentExit = exit;
		Tree.Stm stm = SEQ(s.body.accept(this, _).unNx(), JUMP(next));
		currentNext = oldNext;
		currentExit = oldExit;

		varEnv.endScope();

		return new Exp.Nx(SEQ(init, LABEL(test), exp, LABEL(body), stm,
				LABEL(next), update, JUMP(test), LABEL(exit)));
	}

	public Exp visit(Absyn.MiniJava.Exp.Infix e, Void _) {
		Exp left = e.left.accept(this, _);
		Exp right = e.right.accept(this, _);
		switch (e.op) {
		case AND:
			return new Exp.Cx.IfThenElseExp(left, right, new Exp.Ex(CONST(0)));
		case OR:
			return new Exp.Cx.IfThenElseExp(left, new Exp.Ex(CONST(1)), right);
		case EQ:
			return new Exp.Cx.Rel(Tree.Stm.CJUMP.Operator.BEQ, left.unEx(),
					right.unEx());
		case NE:
			return new Exp.Cx.Rel(Tree.Stm.CJUMP.Operator.BNE, left.unEx(),
					right.unEx());
		case GT:
			return new Exp.Cx.Rel(Tree.Stm.CJUMP.Operator.BGT, left.unEx(),
					right.unEx());
		case GE:
			return new Exp.Cx.Rel(Tree.Stm.CJUMP.Operator.BGE, left.unEx(),
					right.unEx());
		case LT:
			return new Exp.Cx.Rel(Tree.Stm.CJUMP.Operator.BLT, left.unEx(),
					right.unEx());
		case LE:
			return new Exp.Cx.Rel(Tree.Stm.CJUMP.Operator.BLE, left.unEx(),
					right.unEx());
		case ADD:
			return new Exp.Ex(ADD(left.unEx(), right.unEx()));
		case SUB:
			return new Exp.Ex(SUB(left.unEx(), right.unEx()));
		case MUL:
			return new Exp.Ex(MUL(left.unEx(), right.unEx()));
		case DIV:
			return new Exp.Ex(DIV(left.unEx(), right.unEx()));
		}
		throw new Error();
	}

	public Exp visit(Absyn.MiniJava.Exp.Prefix e, Void _) {
		Exp exp = e.exp.accept(this, _);
		switch (e.op) {
		case NEG:
			return new Exp.Ex(SUB(CONST(0), exp.unEx()));
		case NOT:
			return new Exp.Cx.IfThenElseExp(exp, new Exp.Ex(CONST(0)),
					new Exp.Ex(CONST(1)));
		}
		throw new Error();
	}

	public Exp visit(Absyn.MiniJava.Exp.NewArray e, Void _) {
		Tree.Exp exp = null;
		for (Absyn.MiniJava.Exp d : e.dims) {
			if (exp == null)
				exp = d.accept(this, _).unEx();
			else if (d != null)
				throw new Error();
		}

		Temp size = new Temp();
		return new Exp.Ex(ESEQ(MOVE(TEMP(size), exp),
				CALL(NAME(Label.get("new")),
						Exps(MUL(TEMP(size),
								CONST(frame.wordSize())),
								TEMP(size)))));
	}

	private static int methods(INSTANCE i, LinkedHashMap<String, Integer> map) {
		int index = 0;
		if (i.instanceOf.parent != null)
			index += methods(i.instanceOf.parent.instance, map);
		for (String method : i.methods.map.keySet()) {
			if (!map.containsKey(method))
				map.put(method, index++);
		}
		return index;
	}

	private static LinkedHashMap<String, Integer> methods(INSTANCE i) {
		LinkedHashMap<String, Integer> map =
			new LinkedHashMap<String, Integer>();
		methods(i, map);
		return map;
	}

	public Exp visit(Absyn.MiniJava.Exp.Call e, Void _) {
		Tree.Exp exp = e.exp.accept(this, _).unEx();
		Semant.Type t = e.exp.type;
		FUN f = t.method(e.selector.toString());
		if (f == null && t instanceof INSTANCE) {
			t = ((INSTANCE)t).instanceOf;
			f = t.method(e.selector.toString());
		}
		if (t instanceof CLASS) {
			CLASS c = (CLASS) t;
			Tree.Exp[] args = new Tree.Exp[e.actuals.size()];
			int i = 0;
			for (Absyn.MiniJava.Exp a : e.actuals)
				args[i++] = a.accept(this, _).unEx();
			if (f.external != null)
				return new Exp.Ex(CALL(frame.external(f.external), args));
			while (!c.methods.map.containsKey(e.selector.toString()))
				c = c.parent;
			return new Exp.Ex(CALL(NAME(Label.get(c.name + "."
					+ e.selector.toString())), args));
		}
		Tree.Exp[] args = new Tree.Exp[e.actuals.size() + 1];
		int i = 0;
		for (Absyn.MiniJava.Exp a : e.actuals)
			args[++i] = a.accept(this, _).unEx();
		int wordSize = frame.wordSize();
		if (exp == thisExp) {
			args[0] = thisExp;
			int offset =
				methods((INSTANCE) t).get(e.selector.toString()) * wordSize;
			return new Exp.Ex(CALL(MEM(MEM(exp, -wordSize), offset), args));
		}
		if (exp == superExp) {
			args[0] = thisExp;
			LinkedHashMap<String, Label> vtable = vtable((INSTANCE) t);
			return new Exp.Ex(CALL(NAME(vtable.get(e.selector.toString())),
					args));
		}
		Tree.Exp target;
		if (exp instanceof Tree.Exp.TEMP)
			target = exp;
		else {
			target = TEMP(new Temp());
			exp = ESEQ(MOVE(target, exp), target);
		}
		args[0] = target;
		Label badPtr = frame.badPtr();
		if (badPtr != null) {
			Label okPtr = new Label();
			exp =
				ESEQ(SEQ(BEQ(exp, CONST(0), badPtr, okPtr), LABEL(okPtr)),
						target);
		}
		int offset =
			methods((INSTANCE) t).get(e.selector.toString()) * wordSize;
		return new Exp.Ex(CALL(MEM(MEM(exp, -wordSize), offset), args));
	}

	private HashMap<String, Label> strings = new HashMap<String, Label>();

	private Label stringLabel(String s) {
		Label l = strings.get(s);
		if (l != null)
			return l;
		l = new Label();
		strings.put(s, l);
		frags.add(new Frag.Data(frame.string(l, s)));
		return l;
	}

	public Exp visit(Absyn.MiniJava.Exp.Literal e, Void _) {
		String s = e.toString();
		switch (e.kind) {
		case CHAR: {
			char value;
			int i = 0;
			char c;
			if ((c = s.charAt(i++)) != '\'')
				throw new Error();
			if ((c = s.charAt(i++)) == '\\')
				switch (c = s.charAt(i++)) {
				case 'b':
					value = '\b';
					break;
				case 't':
					value = '\t';
					break;
				case 'n':
					value = '\n';
					break;
				case 'f':
					value = '\f';
					break;
				case 'r':
					value = '\r';
					break;
				case '\'':
					value = '\'';
					break;
				case '"':
					value = '\"';
					break;
				case '\\':
					value = '\\';
					break;
				default:
					value = c;
					if ((c = s.charAt(i++)) != '\'') {
						value <<= 3;
						value += c;
						if ((c = s.charAt(i++)) != '\'') {
							value <<= 3;
							value += c;
						}
					}
				}
			else
				value = c;
			if ((c = s.charAt(i++)) != '\'')
				throw new Error();
			return new Exp.Ex(CONST((int) value));
		}
		case STRING: {
			String result = "";
			int i = 0;
			char c;
			if ((c = s.charAt(i++)) != '"')
				throw new Error();
			while ((c = s.charAt(i++)) != '"')
				if (c == '\\')
					switch (c = s.charAt(i++)) {
					case 'b':
						result += '\b';
						break;
					case 't':
						result += '\t';
						break;
					case 'n':
						result += '\n';
						break;
					case 'f':
						result += '\f';
						break;
					case 'r':
						result += '\r';
						break;
					case '\'':
						result += '\'';
						break;
					case '"':
						result += '\"';
						break;
					case '\\':
						result += '\\';
						break;
					default:
						int value = c - '0';
						c = s.charAt(i);
						if (c >= '0' && c <= '7') {
							i++;
							value <<= 3;
							value += c - '0';
							c = s.charAt(i);
							if (c >= '0' && c <= '7') {
								i++;
								value <<= 3;
								value += c - '0';
							}
						}
						result += (char) value;
						break;
					}
				else
					result += c;
			return new Exp.Ex(NAME(stringLabel(result)));
		}
		case DEC:
			return new Exp.Ex(CONST(Integer.parseInt(s, 10)));
		case HEX:
			return new Exp.Ex(CONST(Integer.parseInt(s.substring(2), 16)));
		case OCT:
			return new Exp.Ex(CONST(Integer.parseInt(s, 8)));
		case NULL:
			return new Exp.Ex(CONST(0));
		case FALSE:
			return new Exp.Ex(CONST(0));
		case TRUE:
			return new Exp.Ex(CONST(1));
		}
		throw new Error();
	}

	private static int fields(INSTANCE i, LinkedHashMap<String, Integer> map) {
		int index = 0;
		if (i.instanceOf.parent != null)
			index += fields(i.instanceOf.parent.instance, map);
		if (map == null)
			index += i.fields.map.size();
		else
			for (String field : i.fields.map.keySet())
				map.put(field, index++);
		return index;
	}

	public Exp visit(Absyn.MiniJava.Exp.NewInstance e, Void _) {
		INSTANCE type = (INSTANCE) e.type;
		int size = fields(type, null) * frame.wordSize();
		Label vtable = Label.get(e.classType + "..vtable");
		if (vtable == null)
			throw new Error(e.classType.toString());
		return new Exp.Ex(CALL(NAME(Label.get("new")), Exps(CONST(size),
				NAME(vtable))));
	}

	public Exp visit(Absyn.MiniJava.Exp.This e, Void _) {
		return new Exp.Ex(thisExp);
	}

	public Exp visit(Absyn.MiniJava.Exp.Super e, Void _) {
		return new Exp.Ex(superExp);
	}

	private static LinkedHashMap<String, Integer> fields(INSTANCE i) {
		LinkedHashMap<String, Integer> map =
			new LinkedHashMap<String, Integer>();
		fields(i, map);
		return map;
	}

	public Exp visit(Absyn.MiniJava.Exp.FieldAccess e, Void _) {
		Tree.Exp exp = e.exp.accept(this, _).unEx();
		Semant.Type t = e.exp.type;
		Semant.Type f = t.field(e.selector.toString());
		if (f == null && t instanceof INSTANCE) {
			t = ((INSTANCE)t).instanceOf;
			f = t.field(e.selector.toString());
		}
		if (t instanceof CLASS) {
			CLASS c = (CLASS) t;
			while (!c.fields.map.containsKey(e.selector.toString()))
				c = c.parent;
			int offset = 0;
			for (String s : c.fields.map.keySet()) {
				if (e.selector.toString().equals(s))
					break;
				offset += frame.wordSize();
			}
			return new Exp.Ex(MEM(NAME(Label.get(c.name)), offset));
		}
		int index =
			t instanceof ARRAY ? -1
					: fields((INSTANCE) t).get(e.selector.toString());
		int offset = index * frame.wordSize();
		if (exp == thisExp || exp == superExp)
			return new Exp.Ex(MEM(thisExp, offset));
		Tree.Exp target;
		if (exp instanceof Tree.Exp.TEMP)
			target = exp;
		else {
			target = TEMP(new Temp());
			exp = ESEQ(MOVE(target, exp), target);
		}
		Label badPtr = frame.badPtr();
		if (badPtr != null) {
			Label okPtr = new Label();
			exp =
				ESEQ(SEQ(BEQ(exp, CONST(0), badPtr, okPtr), LABEL(okPtr)),
						target);
		}
		return new Exp.Ex(MEM(exp, offset));
	}

	public Exp visit(Absyn.MiniJava.Exp.Id e, Void _) {
		Frame.Access a = varEnv.get(e.toString());
		if (a == null)
			return new Exp.Ex(CONST(0));
		return new Exp.Ex(a.exp());
	}

	public Exp visit(Absyn.MiniJava.Exp.ArrayAccess e, Void _) {
		Tree.Exp exp = e.exp.accept(this, _).unEx();
		Tree.Exp index = e.index.accept(this, _).unEx();
		Label badSub = frame.badSub();
		Label badPtr = frame.badPtr();
		Label okLo = new Label();
		Label okHi = new Label();
		Temp a = new Temp();
		Temp i = new Temp();
		int size = frame.wordSize();
		Tree.Exp length = MEM(TEMP(a), -size);
		Tree.Stm nullCheck = null;
		Label okPtr = null;
		if (badPtr != null)
			nullCheck =
				SEQ(BEQ(TEMP(a), CONST(0), badPtr, okPtr = new Label()),
						LABEL(okPtr));
		Tree.Stm loCheck =
			SEQ(BLT(TEMP(i), CONST(0), badSub, okLo), LABEL(okLo));
		Tree.Stm hiCheck = SEQ(BGE(TEMP(i), length, badSub, okHi), LABEL(okHi));
		return new Exp.Ex(ESEQ(SEQ(MOVE(TEMP(a), exp), MOVE(TEMP(i), index),
				nullCheck, loCheck, hiCheck),
				MEM(ADD(TEMP(a), MUL(TEMP(i), CONST(size))))));
	}

	private <E extends Absyn.MiniJava> Tree.Stm visit(List<E> l, Void _) {
		Tree.Stm s = null;
		if (l != null)
			for (E e : l)
				s = SEQ(s, e.accept(this, _).unNx());
		return s;
	}

	public Exp visit(Absyn.MiniJava.Name n, Void _) {
		return null;
	}

	public Exp visit(Absyn.MiniJava.Modifier m, Void _) {
		return null;
	}

	public Exp visit(Absyn.MiniJava.Exp.If s, Void _) {
		return new Exp.Cx.IfThenElseExp(s.test.accept(this, _),
				s.thenExp.accept(this, _),
				s.elseExp.accept(this, _));
	}

	public Exp visit(Switch sw, Void dom) {
		return sw.switch_block.accept(this, dom);
	}
	private TreeNode fillTree(ArrayList<TreeNode> nodes, int startIndex, int endIndex){
		if(startIndex<endIndex){
			int medIndex = (startIndex+endIndex)/2;
			TreeNode median = nodes.get(medIndex);
			median.leftChild = fillTree(nodes,medIndex+1,endIndex);
			median.rightChild =  fillTree(nodes,startIndex,medIndex-1);
			return median;
		}
		if(startIndex>=0 && startIndex<nodes.size())
			return nodes.get(startIndex);
		return null;
	}
	
	public Exp visit(SwitchBlock switchBlock, Void dom) {
		if(switchBlock.expressions.size() >= 8){
			TreeNode defaultNode = null;
			int currentIndex = 0;
			ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
			TreeNode prevNode = null;
			Tree.Stm allStatements = null;
			Label prevExit = currentExit;
			currentExit = new Label();
			for (Absyn.MiniJava.Exp ex: switchBlock.expressions) {
				
				TreeNode treeNode = new TreeNode();
				treeNode.myIndex = currentIndex;
				treeNode.nextJump = currentExit;
				// Send my body label to my prev node
				if(prevNode!=null){
					prevNode.nextJump = treeNode.BodyLabel;
				}
				if(currentIndex!=switchBlock.index_of_default){
					//if i am not a default i need a test label
					treeNode.testLabel = new Label();
					treeNode.myValue = ex.value;
					treeNode.valueExpression = ex.accept(this, dom).unEx();
					// Construct the expression here of comparing the expression to the node.
					// if equal jump to the body of this node.
					// if greater jump to the left 
					// if smaller jump to the right
					nodes.add(treeNode);
					
				}
				else{
					prevNode = null;
					treeNode.amIdefault = true;
					defaultNode = treeNode;
					// We don't need to put the default in the tree. although we will construct the node for it
				}
				treeNode.statements = switchBlock.stmlists.get(currentIndex);
				prevNode = treeNode;
				currentIndex++;
			}
			Translate.Tree.Exp switch_expression = switchBlock.switchExp.accept(this, dom).unEx();
			Collections.sort(nodes, new NodeComparator());
			
			// Construct the actual tree here
			fillTree(nodes, 0, nodes.size()-1);
			if(nodes.size()>0){
				allStatements = JUMP(((TreeNode)(nodes.get((nodes.size()-1)/2))).testLabel);
				for(int iter = 0; iter<nodes.size(); iter++){
					allStatements = SEQ(allStatements,
							(((TreeNode)nodes.get(iter)).resolve(this, dom, defaultNode, currentExit,switch_expression)));
					System.out.println("NODE:"+((TreeNode)nodes.get(iter)).myValue);
				}
				if(defaultNode!=null){
					allStatements = SEQ(allStatements,defaultNode.resolve(this, dom, defaultNode, currentExit, null));
				}
				allStatements = SEQ(allStatements,LABEL(currentExit));
			}
			else{
				defaultNode.nextJump = null;
				if(defaultNode!=null){
					allStatements = SEQ(allStatements,defaultNode.resolve(this, dom, defaultNode, currentExit, null));
				}
			}
			Exp expr= new Exp.Nx(allStatements);


			currentExit = prevExit;
			
			return expr;
		}
		else{
			// Do cascaded if statements
			int number_of_cases = switchBlock.expressions.size();
			int current_index; // Moves along the all the case expressions
		
			Tree.Stm statements; // The tree of case statements
			Tree.Stm tests; // The tree of tests
			
			Label exitLabel = new Label();
			Label testLabel = new Label();	
			Label defaultLabel = new Label();
			
			// The following 2 lines adjust the jump address of the break statement, to refer to the end of switch
			Label prevExit = currentExit;
			currentExit = exitLabel;
							
			// Building the block of statements and labels:
			Label[] statementLabels = new Label[number_of_cases];
			Tree.Stm[] statementTrees = new Tree.Stm[number_of_cases]; // The code of each case
			statements = JUMP(testLabel);
			for (current_index = 0; current_index < number_of_cases; current_index++) {
				// Defining the tree of statements of each case:
				statementLabels[current_index] = new Label();
				for (Absyn.MiniJava.Stm stm : switchBlock.stmlists.get(current_index))
					statementTrees[current_index] = SEQ(statementTrees[current_index], stm.accept(this, dom).unNx());   
	
				statements = SEQ(statements, LABEL(statementLabels[current_index]), statementTrees[current_index]);
			}
			
			// The following resets the jump address of the break statement 
			currentExit = prevExit;
			
			// The last statement should be: Jump to exit
			statements = SEQ(statements, JUMP(exitLabel));
					
			Label next = new Label();
			Label prev = new Label();
						
			tests = LABEL(testLabel);
			current_index = 0;
			Translate.Tree.Exp switch_expression = switchBlock.switchExp.accept(this, dom).unEx();
			
			for (Absyn.MiniJava.Exp ex: switchBlock.expressions) {
				if (current_index == number_of_cases - 1) { // last case
					if (switchBlock.index_of_default != current_index) // and it is not a default
					{
						if (switchBlock.index_of_default != -1) // default statement exists
						{
							tests = SEQ(tests, LABEL(next), new CJUMP(Tree.Stm.CJUMP.Operator.BEQ, switch_expression, ex.accept(this, dom).unEx(), statementLabels[current_index], defaultLabel));
							// default statement:
							tests = SEQ(tests, LABEL(defaultLabel), JUMP(statementLabels[switchBlock.index_of_default]));
						}
						else
							tests = SEQ(tests, LABEL(next), new CJUMP(Tree.Stm.CJUMP.Operator.BEQ, switch_expression, ex.accept(this, dom).unEx(), statementLabels[current_index], exitLabel));
					}
					else
						tests = SEQ(tests, LABEL(next), JUMP(statementLabels[switchBlock.index_of_default]));
					
					break;
				}

				if (switchBlock.index_of_default != current_index)
				{
					prev = next;
					next = new Label();
					
					if(current_index != 0) // not first test
						tests = SEQ(tests, LABEL(prev), new CJUMP(Tree.Stm.CJUMP.Operator.BEQ, switch_expression, ex.accept(this, dom).unEx(), statementLabels[current_index], next));
					else
						tests = SEQ(tests, new CJUMP(Tree.Stm.CJUMP.Operator.BEQ, switch_expression, ex.accept(this, dom).unEx(), statementLabels[current_index], next));
				}
				
				current_index++;
			}
			
			return new Exp.Nx(SEQ(statements, tests, LABEL(exitLabel)));
		}
		
	}
}

